package week_07;

/**
 * 312. 戳气球
 * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
 * <p>
 * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
 * 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
 * <p>
 * 求所能获得硬币的最大数量。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * 输入：nums = [3,1,5,8]
 * 输出：167
 * 解释：
 * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
 * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
 * 示例 2：
 * <p>
 * 输入：nums = [1,5]
 * 输出：10
 */
public class MaxCoins_312 {
    public int maxCoins1(int[] input) {
        // 两端补0
        int n = input.length;
        int[] nums = new int[n + 2];
        nums[0] = 1;
        for (int i = 0; i < n; i++) {
            nums[i + 1] = input[i];
        }
        nums[n + 1] = 1;
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 1; len <= n; len++) {
            for (int l = 1; l <= n - len + 1; l++) {
                int r = l + len - 1;
                for (int p = l; p <= l; p++) {
                    dp[l][r] = Math.max(dp[l][r], dp[l][p - 1] + dp[p + 1][r] + nums[p] * nums[l - 1] * nums[r + 1]);
                }
            }
        }
        return find(dp, nums, 1, n);
    }

    public int maxCoins2(int[] input) {
        // 时间复杂度过高 需要减半 优化计算
        // 两端补0
        int n = input.length;
        int[] nums = new int[n + 2];
        nums[0] = 1;
        for (int i = 0; i < n; i++) {
            nums[i + 1] = input[i];
        }
        nums[n + 1] = 1;
        int[][] dp = new int[n + 1][n + 1];
        return find(dp, nums, 1, n);
    }


    public int find(int[][] dp, int[] nums, int l, int r) {
        if (l > r) return 0;
        if (dp[l][r] > 0) return dp[r][r];
        for (int p = l; p <= r; p++) {
            dp[l][r] = Math.max(dp[l][r], find(dp, nums, l, p - 1) + find(dp, nums, p + 1, r) + nums[p] * nums[l - 1] * nums[r + 1]);
        }
        return dp[l][r];
    }
}
